#leetcode题目63：不同路径ii
#难度：中等
#时间复杂度：O(m*n)
#空间复杂度：O(m*n)
#方法：动态规划


from typing import List
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m=len(obstacleGrid)
        n=len(obstacleGrid[0])
        if m<0 or n<0:
            return 0
        if obstacleGrid[0][0]==1:
            return 0
        dp=[[0]*(n+1) for _ in range(m+1)]

        for i in range(m+1):
            for j in range(1,n+1):
                if i==1 and j==1:
                    dp[i][j]=1
                    continue
                if obstacleGrid[i-1][j-1]==1:
                    dp[i][j]=0
                else:
                    dp[i][j]=dp[i-1][j]+dp[i][j-1]

        return dp[-1][-1]

#测试数据
obstacleGrid=[[0,0,0],[0,1,0],[0,0,0]]
#预期输出：2
solution=Solution()
print(solution.uniquePathsWithObstacles(obstacleGrid))

obstacleGrid=[[0,1],[0,0]]
#预期输出：1
solution=Solution()
print(solution.uniquePathsWithObstacles(obstacleGrid))
